home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Reference Guide / C-C++ Interactive Reference Guide.iso / c_ref / csource3 / 181_01 / cforum.1_1 < prev    next >
Encoding:
Text File  |  1986-01-09  |  6.4 KB  |  172 lines
  1. Reprinted from: Micro/Systems Journal, Volume 1. No. 1. March/April 1985
  2. -----------------------------------------------------------------
  3. Copy of back issue may be obtained for $4.50 (foreign $6) from:
  4. Subscriptions are $20/yr, $35/2yrs domestic (published bimonthly)
  5. Micro/Systems Journal
  6. Box 1192
  7. Mountainside NJ 07092
  8. -----------------------------------------------------------------
  9. Copyright 1986
  10. Micro/Systems Journal, Box 1192, Mountainside NJ 07092
  11. This software is released into the public domain for
  12.  non-commercial use only.
  13. -----------------------------------------------------------------
  14.  
  15.  
  16.  
  17.                            THE C FORUM                           
  18.                                by
  19.                             Don Libes
  20.  
  21.  
  22.     What a relief that C is such a "small" language.  Few 
  23. keywords or restrictions to worry about.  No complex operators or 
  24. datatypes to mishandle.  The language is surprisingly svelte for 
  25. all its power.  But while you were able to pick up a book on C 
  26. and breeze through the first half, you may never have gotten very 
  27. comfortable with it, even if you're fluent in another programming 
  28. language.
  29.      Why?  C abounds with subtleties that are written between the 
  30. lines in the UNIX manuals and most of the C language books that 
  31. I've seen.  One of the best places to really see these brought 
  32. out are the experienced C programmer's code.  They know all the 
  33. tricks.  If they were nice enough to leave comments, we might 
  34. learn them also!
  35.      As UNIX is being distributed more and more in binaries form, 
  36. it is difficult to learn from UNIX source code samples.  
  37. Fortunately, many books have come out to fill the void and since 
  38. they were written for the purpose of education, you would think 
  39. they could do the job a lot better.  But most of them slanted 
  40. towards an introduction, while other are references.  Very few 
  41. discuss intermediate-level topics in detail.  That is what this 
  42. column will cover.
  43.      You are encouraged to write to me about topics or problems 
  44. that you want to know about.  I want this column to be reader 
  45. driven.  Until it is, I will write about topics that I'm sure are 
  46. of general interest.  I just happen to have one here!
  47.  
  48. VARIABLY-SIZED ARRAYS
  49. If you've ever written generic subroutines that operate on 
  50. arrays, you've probably run across the problem of trying to pass 
  51. arrays of arbitrary sizes.  For example, suppose we would like to 
  52. have a routine that prints out matrices of arbitrary sizes.  We 
  53. start out:
  54.  
  55. print_array(array)
  56. int array[][];
  57.  
  58.      The C compiler doesn't accept this.  (Mine prints out "null 
  59. dimension".)  This is because arrays are stored without 
  60. information such as the number of rows and columns.  Well, then 
  61. lets try adding the size of the array to the parameters.
  62.  
  63. print_array(array,r,c)
  64. int array[r][c];
  65.  
  66.      The C compiler rejects this also, saying "constant 
  67. expected".  Variable sizes must be constant in C.  What a pain!
  68.      There are several ways of getting arbitrarily sized arrays, 
  69. however.
  70.      One way is to do the addressing yourself.  With the help of 
  71. a macro, this solution is readable.
  72.  
  73. #define MAT(x,y) mat[x*c + y]
  74.  
  75. print_matrix(mat,r,c)
  76. int *mat;
  77. int r, c;
  78. {
  79. int i, j;
  80.  
  81. for (i = 0; i < r; i++) {
  82. for (j = 0; j < c; j++) {
  83. printf("%d ",MAT(i,j));
  84. }
  85. putchar('\n');
  86. }
  87. }
  88.  
  89.      Now, we can declare the matrix and call our routine as 
  90. follows:
  91.  
  92. int matrix[ROWS][COLUMNS];
  93.  
  94. print_matrix(matrix,ROWS,COLUMNS);
  95.  
  96.      The main drawback to this solution is that its time-
  97. expensive.  Each time you reference the array, you perform a 
  98. multiplication and addition.  Thus, to access every member in the 
  99. array requires ROWSxCOLUMNS multiplications.  The other drawback 
  100. is that the macro MAT requires the number of columns being 
  101. available.  We can do better.
  102.      You may never have realized that it isn't necessary  to 
  103. perform those multiplications, simply because it seems inherent 
  104. in figuring out matrix element addresses.  However, if we are 
  105. willing to sacrifice some storage we can avoid the 
  106. multiplication.
  107.      What we do is calculate the addresses for the base of each 
  108. row once and store them in a separate (one-dimensional) array.  
  109. Then we can get to any element simply by adding the column offset 
  110. to the base address of the appropriate row.
  111.      For example, a 5x3 array would require a 5 element "dope 
  112. vector".  Each element of the dope vector is an address of 3 
  113. elements of the array.
  114.      Since we can get to every element of the matrix through the 
  115. dope vector, there is no need to pass the array itself.  So the 
  116. first argument becomes the dope vector.  (Its still called "mat" 
  117. though.)
  118.      Now print_matrix() looks like this:
  119.  
  120. print_matrix(mat,r,c)
  121. int *mat[];/* dope vector: array of pointers to ints */
  122. int r,c;/* rows and columns */
  123. {
  124. int i, j;
  125.  
  126. for (i=0;i<r;i++) {
  127. for (j=0;j<c;j++) {
  128. printf("%d ",mat[i][j]);
  129. }
  130. putchar('\n');
  131. }
  132. }
  133.  
  134.      This type of array takes a little more work to set up:
  135.  
  136. int *matrix[ROWS];/* this is the dope vector */
  137. int i;
  138.  
  139. /* now initialize each pointer in the dope vector */
  140. for (i = 0 ; i < ROWS ; i++ ) {
  141. /* allocate space for the columns */
  142. matrix[i] = (int *) malloc(COLUMNS * sizeof(int));
  143. }
  144.  
  145. print_matrix(matrix,ROWS,COLUMNS);
  146.  
  147.      This technique has the disadvantages that it takes up a 
  148. little more space than a true array and it requires 
  149. initialization (though you can create a subroutine to do this for 
  150. you).
  151.  
  152.      But the advantages are many.  Its faster than real arrays 
  153. because no multiplication is performed to do addressing.  Each 
  154. row can have a different number of elements.  Applications of 
  155. this are to store different length strings in an array or keeping 
  156. an open hash table.
  157.  
  158.      This technique also extends to higher dimensioned arrays 
  159. (where time savings become even better). Also, these arrays can 
  160. be created dynamically.  A final goodie that I'll mention is that 
  161. by adjusting the dope vector (or the pointer to it), its possible 
  162. to get 1-based (or any number) indices rather than 0.
  163.  
  164. Don Libes
  165. seismo!nbs-amrf!libes
  166.  
  167. ---------------------------------------------------------------
  168.      Don Libes is a computer scientist working in the Washington 
  169. DC area.  He works on artifical intelligence as applied to 
  170. robotic networking systems.  He is also the son of Lennie and Sol 
  171. Libes.
  172.